package astoliarskyi.lab2;

public class ParallelMergesort {
	
	private final int threadsNumber;
	private volatile int threadsLeft;
	
	public static void main(String[] args) {
		int[] testArray = new int[1000];
		int min = -1000;
		int max = 1000;
		for (int i=0; i<testArray.length; i++){
			int random = min + (int)(Math.random() * ((max - min) + 1));
			testArray[i] = random;
		}
		ParallelMergesort mergesort = new ParallelMergesort(8);
		int[] sorted = mergesort.sort(testArray);
		for (int i : sorted)
			System.out.println(i);
	}
	
	public ParallelMergesort(int threadsNumber){
		this.threadsNumber = threadsNumber;
	}
	
	public int[] sort(int[] array){
		threadsLeft = threadsNumber - 1; //minus current thread
		return doSort(array);
	}
	
	private int[] doSort(int[] array){
		if (array.length > 1){
			int medium = array.length/2;
			int[] left = new int[medium];
			System.arraycopy(array, 0, left, 0, medium);
			int[] right = new int[array.length - medium];
			System.arraycopy(array, medium, right, 0, array.length - medium);
			
			boolean startInNewThread = false;
			if (right.length > 3){
				synchronized (this) {
					if (threadsLeft > 0){
						threadsLeft = threadsLeft - 1;
						startInNewThread = true;
					}
				}
			}
			if (startInNewThread){
				SortTask task = new SortTask(right);
				Thread threadForRightTask = new Thread(task);
				threadForRightTask.start();
				left = doSort(left);
				try {
					threadForRightTask.join();
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
				synchronized (this) {
					threadsLeft++;
				}
				array = merge(left, task.getResult());
			} else {
				array = merge(doSort(left), doSort(right));
			}
		}
		return array;
	}
	
	private int[] merge(int[] left, int[] right){
		int[] result = new int[left.length + right.length];
		int leftPosition = 0;
		int rightPosition = 0;
		int resultPosition = 0;
		while (leftPosition < left.length | rightPosition < right.length){
			if (leftPosition >= left.length) {
				System.arraycopy(right, rightPosition, result, resultPosition, right.length - rightPosition);
				rightPosition = right.length;
			} else if (rightPosition >= right.length){
				System.arraycopy(left, leftPosition, result, resultPosition, left.length - leftPosition);
				leftPosition = left.length;
			} else {
				if (left[leftPosition] < right[rightPosition])
					result[resultPosition++] = left[leftPosition++];
				else 
					result[resultPosition++] = right[rightPosition++];
			}
		}

		return result;
	}
	
	private class SortTask implements Runnable{
		
		private int[] array;
		
		public SortTask(int[] array){
			this.array = array;
		}
		
		@Override
		public void run() {
			array = ParallelMergesort.this.doSort(array);
		}
		
		public int[] getResult(){
			return array;
		}
		
	}
}
